package com.LeeCode;

import java.util.Arrays;

/**
 * 两球之间的磁力
 */

public class Code1552 {
    public static void main(String[] args) {
        int[] position = {5, 4, 3, 2, 1, 1000000000};
        int m = 2;
        System.out.println(new Code1552().maxDistance(position, m));
    }

    public int maxDistance(int[] position, int m) {
        Arrays.sort(position);
        int left = 0, right = (position[position.length - 1] - position[0]) / (m - 1) + 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (check(position, m, mid))
                left = mid;
            else
                right = mid;
        }
        return left;
    }

    public boolean check(int[] position, int m, int mindiff) {
        int count = 1, previous = position[0];
        int target = previous + mindiff;
        for (int i = 1; i < position.length; i++) {
            if (position[i] >= target) {
                count++;
                previous = position[i];
                target = previous + mindiff;
            }
            if (count >= m)
                return true;
        }
        return false;
    }
}
